/**
 * @Question.Title: 最大整除子集
 * @Question.No: 368
 * @Author: Dang Qi
 * @Date: 2021-04-23 00:28:04
 * @Description: 
 */
//给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[
//j]) 都应当满足：
// 
// answer[i] % answer[j] == 0 ，或 
// answer[j] % answer[i] == 0 
// 
//
// 如果存在多个有效解子集，返回其中任何一个均可。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[1,2]
//解释：[1,3] 也会被视为正确答案。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,4,8]
//输出：[1,2,4,8]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 1 <= nums[i] <= 2 * 109 
// nums 中的所有整数 互不相同 
// 
// Related Topics 数学 动态规划 
// 👍 218 👎 0

package dq.leetcode.editor.cn;

import java.util.*;

public class LargestDivisibleSubset {
    public static void main(String[] args) {
        Solution solution = new LargestDivisibleSubset().new Solution();
        int[] nums = {1};

        System.out.println(solution.largestDivisibleSubset(nums));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        // 记录以当前为结尾的最长的子集的数量
        int[] f = new int[nums.length];
        // 记录以当前为结尾的最长子集的上一个元素
        int[] g = new int[nums.length];
        //用来记录最长子集的长度
        int maxLenIndex = 0;
        // 初始化数组，上一个元素默认为自己，并且当前默认最长为 1
        for(int i = 0; i < nums.length; i++){
            f[i] = 1;
            g[i] = i;
        }
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < i; j++){
                //整除, 找到长度比当前大的子集
                if(nums[i] % nums[j] == 0 && f[i] < f[j] + 1){
                    f[i] = f[j] + 1;
                    g[i] = j; //将当前的上一个更新
                    maxLenIndex = f[maxLenIndex] > f[i] ? maxLenIndex : i;
                }
            }
        }
        List<Integer> ans = new LinkedList<>();
        while (g[maxLenIndex] != maxLenIndex){
            ans.add(0, nums[maxLenIndex]);
            maxLenIndex = g[maxLenIndex];
        }
        ans.add(0, nums[maxLenIndex]);
        return ans;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}